package dataS.tree;

public class BinaryTree {
    public Node root;

    public BinaryTree() {
        root = null;
    }

    public void insert(int value, String sdata) {

        Node newNode = new Node(value, sdata);
        Node tmp = root;
        Node parent;
        if (root == null) {
            root = newNode;
            return;
        } else {
            while (true) {
                parent = tmp;
                //找到插入位置
                if (value > tmp.data) {
                    tmp = tmp.rightChild;
                    //此处需要根据保存的父节点进行插入，插入后就return
                    if (tmp == null) {
                        parent.rightChild = newNode;
                        return;
                    }
                } else {
                    tmp = tmp.leftChild;
                    if (tmp == null) {
                        parent.leftChild = newNode;
                        return;
                    }
                }
            }
        }
    }

    public boolean delete(int value) {
        //首先找到要删除的节点及其父节点

        //该节点是叶子节点，父节点子节点置空

        //该节点只有一个子节点（是左还是右），父节点指向子节点

        //该节点有俩个子节点，需要找到删除节点的中序后继节点
        return true;

    }
    //找到某个节点的中序后继结点
    public Node findInOrderNode(Node node){

        return null;

    }

    public void update(int value) {

    }

    //查找节点
    public Node find(int value) {
        Node tmp = root;
        if (root == null)
            return null;
        while (tmp.data != value) {
            if (value > tmp.data) {
                tmp = tmp.rightChild;
            } else {
                tmp = tmp.leftChild;
            }
            if (tmp == null)
                return null;
        }
        return tmp;
    }



    //前序遍历，根左右
    public void preOrder(Node root) {
        if (root == null)
            return;
        System.out.println(root.sdata + "," + root.data);
        preOrder(root.leftChild);
        preOrder(root.rightChild);

    }

    //中序遍历，左根右
    public void inOrder(Node root) {
        if (root == null)
            return;

        inOrder(root.leftChild);
        System.out.println(root.sdata + "," + root.data);
        inOrder(root.rightChild);

    }

    //后序遍历，左右根
    public void postOrder(Node root) {
        if (root == null)
            return;

        postOrder(root.leftChild);
        postOrder(root.rightChild);
        System.out.println(root.sdata + "," + root.data);

    }

}
